算法选择向导是有效且通用的工具，它们会自动选择有关该问题和可用计算资源的高级信息的优化算法，例如决策变量的数量和类型，最大程度的评估数量，并行评估等。艺术算法选择向导很复杂且难以改进。我们在这项工作中建议使用自动配置方法来通过找到构成它们的算法的更好配置来改善其性能。特别是，我们使用精英迭代赛车（IRACE）来找到特定人工基准测试的CMA配置，这些基准取代了Nevergrad平台提供的NGOPT向导中当前使用的手工制作的CMA配置。我们详细讨论了IRACE的设置，目的是生成在每个基准内的各种问题实例集合中都可以正常工作的配置。我们的方法也提高了NGOPT向导的性能，即使在不属于Irace的一部分的基准套件上。
translated by 谷歌翻译
在实际优化方案中，要求我们解决的问题实例可能会在优化过程中发生变化，例如，当可用新信息或环境条件发生变化时。在这种情况下，人们可以希望通过从最佳解决方案的最佳解决方案继续进行搜索来实现合理的绩效。同样，人们可能希望，在解决彼此相似的几个问题实例时，````温暖启动'''第二个实例的优化过程是通过第一个实例的最佳解决方案的优化过程。但是，在[Doerr等人，GECCO 2019]中显示，即使使用结构良好的解决方案初始化，进化算法也可能具有通过结构上更糟糕的解决方案替换这些良好溶液的趋势，从而导致优化时间与没有优化的时间相比没有优化的时间。相同的算法从头开始。 Doerr等人。还提出了一种克服这个问题的多样性机制。他们的方法平衡了围绕当前问题的最佳解决方案的贪婪搜索，并在上一个实例的最佳发现解决方案周围进行搜索。在这项工作中，我们首先表明Doerr等人建议的重新优化方法。当问题实例容易发生更频繁的更改时，达到限制。更确切地说，我们证明它们被陷入了动态领导问题问题，目标字符串定期更改。然后，我们提出了其算法的修改，该算法在围绕先前最佳和当前最佳解决方案围绕贪婪的搜索进行了插值。我们从经验上评估了具有各种变化频率和不同扰动因素的前导者实例上的平滑重优化算法，并表明它表现出优于完全重新启动的（1+1）进化算法和Doerr等人的重新挑选方法。
translated by 谷歌翻译
贝叶斯优化（BO）是一种基于替代物的全球优化策略，依靠高斯流程回归（GPR）模型来近似目标函数和采集功能，以建议候选点。众所周知，对于高维问题，BO不能很好地扩展，因为GPR模型需要更多的数据点才能实现足够的准确性，并且在高维度中，获取优化在计算上变得昂贵。最近的几项旨在解决这些问题的旨在，例如，实现在线变量选择的方法或对原始搜索空间的较低维度次级manifold进行搜索。本文提出了我们以前的PCA-BO的工作，该作品学习了线性子字节，因此提出了一种新颖的内核PCA辅助BO（KPCA-BO）算法，该算法将非线性子词嵌入搜索空间中并在搜索空间中执行BO这个子manifold。直观地，在较低维度的子序列上构建GPR模型有助于提高建模准确性，而无需从目标函数中获得更多数据。此外，我们的方法定义了较低维度的子元素的采集函数，从而使采集优化更易于管理。我们将KPCA-BO与香草bo的性能以及有关可可/BBOB基准套件的多模式问题的PCA-BO进行了比较。经验结果表明，在大多数测试问题上，KPCA-BO在收敛速度方面都优于BO，并且当维度增加时，这种好处变得更加显着。对于60D功能，KPCA-BO在许多测试用例中取得比PCA-BO更好的结果。与Vanilla BO相比，它有效地减少了训练GPR模型所需的CPU时间并优化与香草BO相比的采集功能。
translated by 谷歌翻译
进化算法的运行时间分析最近在将算法性能与算法参数联系起来方面取得了重大进展。但是，研究问题参数的影响的设置很少见。最近提出的W模型为此类分析提供了一个良好的框架，从而生成了具有可调属性的伪树状优化问题。我们通过研究其一种特性（中立性）如何影响随机局部搜索的运行时间来启动W模型的理论研究。中立性通过首先对解决方案候选者的子集进行多数投票，然后通过低级健身函数评估较小维的字符串，从而在搜索空间中创建高原。我们证明，对于此大多数问题，在其整个参数频谱上，随机局部搜索的预期运行时间是上限。为此，我们提供了一个适用于许多优化算法的定理，该定理将多数的运行时间与其对称版本hasmajority联系起来，其中需要足够多数来优化子集。我们还介绍了经典漂移定理的广义版本以及Wald方程的广义版本，我们认为这两个都具有独立的兴趣。
translated by 谷歌翻译
每种算法选择旨在为给定的问题实例和给定的性能标准推荐一种或几种合适的算法，这些算法有望在特定设置中表现良好。选择是经典的离线完成的，使用有关问题实例或在专用功能提取步骤中从实例中提取的功能的公开可用信息。这忽略了算法在优化过程中积累的有价值的信息。在这项工作中，我们提出了一种替代性的在线算法选择方案，我们每次算法选择该方案。在我们的方法中，我们使用默认算法启动优化，在经过一定数量的迭代之后，从该初始优化器的观察到的轨迹中提取实例功能，以确定是否切换到另一个优化器。我们使用CMA-E作为默认求解器测试这种方法，以及六个不同优化器的投资组合作为可切换的潜在算法。与其他关于在线人均算法选择的最新工作相反，我们使用在第一个优化阶段累积的信息进行了第二个优化器。我们表明，我们的方法的表现优于静态算法选择。我们还基于探索性景观分析和分别对CMA-ES内部状态变量的探索性景观分析和时间序列分析进行比较。我们表明，这两种功能集的组合为我们的测试用例提供了最准确的建议，该建议是从可可平台的BBOB功能套件和Nevergrad平台的Yabbob Suite中获取的。
translated by 谷歌翻译
到目前为止，景观感知算法选择方法主要依靠景观特征提取作为预处理步骤，而与投资组合中优化算法的执行无关。这引入了许多实用应用的计算成本的重要开销，因为通过采样和评估手头的问题实例提取和计算功能，与优化算法在其搜索轨迹中所执行的功能类似。如Jankovic等人所建议的。 （EVOAPPS 2021），基于轨迹的算法选择可以通过从求解器在优化过程中对求解器进行采样和评估的点来计算景观特征来规避昂贵的特征提取问题。以这种方式计算的功能用于训练算法性能回归模型，然后在该模型上构建每运行算法选择器。在这项工作中，我们将基于轨迹的方法应用于五种算法的投资组合。我们研究了在固定的功能评估预算之后预测不同算法性能的情况下，性能回归和算法选择模型的质量和准确性。我们依靠使用相同功能评估的上述预算的一部分计算出的问题实例的景观特征。此外，我们考虑一次在求解器之间切换一次的可能性，这要求它们要热身启动，即当我们切换时，第二求解器继续使用第一个求解器收集的信息来继续适当地初始化优化过程。在这种新背景下，我们展示了基于轨迹的每算法选择的有前途的表现，并启动了温暖。
translated by 谷歌翻译
现代优化策略，例如进化算法，蚂蚁菌落算法，贝叶斯优化技术等。带有几个参数，可在优化过程中引导其行为。为了获得高性能算法实例，已经开发了自动化算法配置技术。最受欢迎的工具之一是IRACE，它可以评估顺序种族中的配置，利用迭代统计测试来丢弃性能不佳的配置。在比赛结束时，使用贪婪的截断选择，从未丢弃的幸存者配置中选择了一组精英配置。我们研究两种替代选择方法：一种是保持最佳幸存者，并从一组幸存者中随机选择其余配置，而另一个则应用熵以最大程度地提高精英的多样性。这些方法经过测试，用于调整蚂蚁菌落优化算法，以解决旅行销售人员问题以及二次分配问题，并为满足性问题调整精确的树搜索求解器。实验结果表明，与IRACE的默认选择相比，测试的基准测试结果有所改善。此外，获得的结果表明，非专业人士可以获得多种算法配置，这鼓励我们探索更广泛的解决方案以了解算法的行为。
translated by 谷歌翻译
我们展示IohexPerimener，Iohprofiler项目的实验模块，旨在为基准测试迭代优化启发式提供易于使用和高度可定制的工具箱，例如进化和遗传算法，本地搜索算法，贝叶斯优化技术等。Iohexperimenter可以用作独立工具或作为基准管道的一部分，用于使用IOHPOFILER（如IOHANALYZER）的其他组件，该模块用于交互式性能分析和可视化。 iohExperimenter在优化问题和求解器之间提供了有效的接口，同时允许优化过程的粒度测井。这些日志与现有的交互式数据分析工具完全兼容，这显着加快了基准管道的部署。 iohexperimener的主要组成部分是构建定制的问题套件和各种日志记录选项的环境，允许用户转向数据记录的粒度。
translated by 谷歌翻译
基准和性能分析在理解迭代优化启发式（IOHS）的行为中发挥着重要作用，例如本地搜索算法，遗传和进化算法，贝叶斯优化算法等。然而，这项任务涉及手动设置，执行和分析实验单独的基础，这是艰苦的，可以通过通用和设计精心设计的平台来缓解。为此，我们提出了Iohanalyzer，一种用于分析，比较和可视化IOH的性能数据的新用户友好的工具。在R和C ++中实现，Iohanalyzer是完全开源的。它可以在Cran和GitHub上获得。 Iohanalyzer提供有关固定目标运行时间的详细统计信息以及具有实际值的Codomain，单目标优化任务的基准算法的固定预算性能。例如，在多个基准问题上的性能聚合是可能的，例如以经验累积分布函数的形式。 Iohanalyzer在其他性能分析包上的主要优点是其高度交互式设计，允许用户指定对其实验最有用的性能测量，范围和粒度，以及不仅分析性能迹线，还可以分析演变动态状态参数。 Iohanalyzer可以直接从主基准平台处理性能数据，包括Coco平台，JOVERRAD，SOS平台和iohExperenter。提供R编程接口，供用户更倾向于对实现的功能进行更精细的控制。
translated by 谷歌翻译
第五个成功规则是控制进化算法参数的最着名和最广泛接受的技术之一。虽然它经常在字面意义上应用，但一个共同的解释将五分之一的成功规则视为一系列基于成功的更新规则，这些规则由更新强度$ F $和成功率决定。在这方面，我们分析了（1 + 1）进化算法在领导者上的性能取决于这两个超参数。我们的主要结果表明，为小型更新优势获得最佳性能$ f = 1 + o（1）$和成功率$ 1 / e $。我们还证明，除了下订单术语之外，通过该参数设置获得的运行时间，通过最佳的健身依赖率实现的相同。我们对（1 + 1）进化算法的重新采样变体显示了类似的结果，该算法强制实施每次迭代至少一位。
translated by 谷歌翻译